package programmercarl.动态规划.C13;

import java.util.Arrays;

class Solution1 {
    public boolean canPartition(int[] nums) {
        if(null==nums||nums.length==1||nums.length==0) return false;
        int sum=Arrays.stream(nums).sum();
        if(sum%2!=0) return false;
        int target=sum/2;
        int len=nums.length;
        //target背包所能放下i-1的数量
        int[] dp=new int[target+1];
        for(int i=0;i<len;i++){
            for(int j=target;j>=nums[i]&&j>=0;j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;
    }
}